from collections import deque
from typing import List

# 会相交的情况
CRASH_STATUS = {
    "": set(),
    "EN": {"WN", "SN"},
    "EW": {"NW", "NS", "NE", "WN", "SW", "SN"},
    "ES": {"NS", "NE", "WE", "WS", "SW", "SN"},
    "SE": {"NE", "WE"},
    "SN": {"ES", "EW", "EN", "NE", "WE", "WN"},
    "SW": {"EW", "ES", "NW", "NS", "WE", "WN"},
    "WS": {"ES", "NS"},
    "WE": {"SW", "SN", "SE", "ES", "NS", "NE"},
    "WN": {"SN", "SW", "EW", "EN", "NS", "NE"},
    "NW": {"SW", "EW"},
    "NS": {"WS", "WE", "WN", "SW", "ES", "EW"},
    "NE": {"WE", "WN", "SE", "SN", "EW", "ES"}
}

choice = [
    [True, True, True, True],
    [True, True, True, False],
    [True, True, False, True],
    [True, True, False, False],
    [True, False, True, True],
    [True, False, True, False],
    [True, False, False, True],
    [True, False, False, False],
    [False, True, True, True],
    [False, True, True, False],
    [False, True, False, True],
    [False, True, False, False],
    [False, False, True, True],
    [False, False, True, False],
    [False, False, False, True]
]


def all_chance(ways):
    for choose in choice:
        ban = set()
        for i in range(4):
            if choose[i]:
                ban |= CRASH_STATUS[ways[i]]
        for i in range(4):
            if choose[i] and ways[i] in ban:
                break
        else:
            yield choose


class Solution:
    def trafficCommand(self, directions: List[str]) -> int:
        n0, n1, n2, n3 = len(directions[0]), len(directions[1]), len(directions[2]), len(directions[3])

        cars0 = ["E" + ch for ch in directions[0]]  # 东
        cars1 = ["S" + ch for ch in directions[1]]  # 南
        cars2 = ["W" + ch for ch in directions[2]]  # 西
        cars3 = ["N" + ch for ch in directions[3]]  # 北

        # print(cars0, cars1, cars2, cars3)

        # dp = [[[[81] * n3 for _ in range(n2)] for _ in range(n1)] for _ in range(n0)]
        # dp[0][0][0][0] = 0

        visited = {(0, 0, 0, 0)}
        queue = deque([(0, 0, 0, 0)])

        time = 0
        while queue:
            # 判断当前是否已经到达终点
            if (n0, n1, n2, n3) in visited:
                return time

            time += 1

            for _ in range(len(queue)):
                m0, m1, m2, m3 = queue.popleft()

                ways = [""] * 4
                if m0 < n0:
                    ways[0] = cars0[m0]
                if m1 < n1:
                    ways[1] = cars1[m1]
                if m2 < n2:
                    ways[2] = cars2[m2]
                if m3 < n3:
                    ways[3] = cars3[m3]

                # print((m0, m1, m2, m3), ":", ways, len(list(all_chance(ways))))

                for b0, b1, b2, b3 in all_chance(ways):

                    t0, t1, t2, t3 = m0, m1, m2, m3

                    if b0 and m0 < n0:
                        t0 += 1
                    if b1 and m1 < n1:
                        t1 += 1
                    if b2 and m2 < n2:
                        t2 += 1
                    if b3 and m3 < n3:
                        t3 += 1

                    if (t0, t1, t2, t3) not in visited:
                        queue.append((t0, t1, t2, t3))
                        visited.add((t0, t1, t2, t3))

            print(len(queue), queue)


if __name__ == "__main__":
    print(Solution().trafficCommand(directions=["W", "N", "ES", "W"]))  # 2
    print(Solution().trafficCommand(directions=["NS", "WE", "SE", "EW"]))  # 3
